package com.lwl.Algorithmic_data_structure.class17经典递归;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lwl
 * @Description 获取所有子序列
 * @date 2023/6/2 11:22
 */
public class Code02getAllSubSequences {

    public static void main(String[] args) {
        for (String str : getAllSubSequences("abcd")) {
            System.out.println(str);
        }
    }

    static public List<String> getAllSubSequences(String strs) {
        ArrayList<String> ans = new ArrayList<>();
        process(strs.toCharArray(), 0, ans, "#");
        return ans;
    }

    /**
     * @param strs      字符数组
     * @param curIdx    当前下表
     * @param ans       当前的所有子序列集合
     * @param beforeStr 当前子序列（还未构建完成的子序列,到字符数组末尾才算完成）
     */
    static private void process(char[] strs, int curIdx, ArrayList<String> ans, String beforeStr) {
        if (curIdx == strs.length) {
            ans.add(beforeStr);
            return;
        }
        String newStr = beforeStr + strs[curIdx];
        process(strs, curIdx + 1, ans, newStr);
        process(strs, curIdx + 1, ans, beforeStr);
    }

}
